package offer.day9;

public class No13movingCount {
    /*
     * 面试题13：机器人的运动范围
     * 题目：地上有一个m行n列的方格。一个机器人从坐标（0，0）的格子开始移动，
     *     它每次可以向上、下、左、右移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子
     *     例如：当k为18时，机器人能够进入方格为（35，37），因为3+5+3+7=18.
     *         但它不能进（35，38），因为3+5+3+8=19.
     *         请问该机器人能够到达多少个格子
     *
     *
     *
     *思路：用一个flag标志位标记是否已经进入过该格子
     *	 声明一个全局变量可以统计能进的坐标的数量
     *	  然后从（0，0）开始计算，先标记这个格子，在进行查看周围的格子
     *	 并计算是否位数和大于k，若大于则可能进入，否则可以进入
     *   对此位置的上下左右递归进行查询，直到所有的统计完
     * */

    static int k=1,res=0;
    static boolean[][] flag;

    public static void main(String[] args) {
        int m=2,n=3;
        int[][] matrix = new int[m][n];
        flag=new boolean[m][n];
        showMatrix(matrix);
        System.out.println();

        helper(matrix,0,0);
        System.out.println(res);

    }

    public static void helper(int[][] matrix, int i, int j) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || sumDigit(i) + sumDigit(j) > k || flag[i][j]==true) {
            return ;
        }
        res++;
        flag[i][j]=true;
        helper(matrix,i+1,j);
        helper(matrix,i,j+1);
        flag[i][j] = false;

    }

    public static int sumDigit(int val) {
        int res = 0;
        while (val > 0) {
            res += val % 10;
            val = val / 10;
        }
        return res;
    }

    public static void showMatrix(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}
